package algorithms;

/**
 * 求自身的后缀匹配的最长真前缀，真前缀意味着不能是自身的全部
 */
public class 最长前后缀 {

    public static void main(String[] args) {
        long start = System.nanoTime();
        String ababab = computeLongestPrefix("ababa");
        long end = System.nanoTime();
        System.out.println("time is : " + (end - start) / 1000 + "微秒");
        System.out.println(ababab);
    }

    private static String computeLongestPrefix(String s) {
        if (s.length() <= 1) {
            return "";
        }

        /**
         * 因为是寻找最长真前缀，先从i=1开始的字符串判断。
         * ababab
         *  ababab
         *   ababab
         */
        for (int i = 1; i < s.length(); i++) {
            int k = 0;
            int j = i;
            /**
             * 用j表示后缀
             * 用k表示前缀
             */
            while (j < s.length() && s.charAt(k) == s.charAt(j)) {
                k++;
                j++;
            }
            if (j < s.length()) {
                //没有匹配到最后，表明当前从i开始的后缀不是字符串的前缀，继续i+1匹配
                continue;
            }
            //匹配到最后
            return s.substring(i);
        }
        return "";
    }


}
